/*******************************************************************************
* FileName:         BinTree.cpp
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/11/20 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #8
*******************************************************************************/

#include "BinTree.h"
#include <iostream>
#include <vector>
#include <algorithm>

BinTree::BinTree(){
    root = nullptr;
    count = 0;
    depth = 0;
    current_id = 1;   //新节点置为1

}

void BinTree::deletetree(node* n){
    //迭代删除节点
    if(n){
        deletetree(n -> left);
        deletetree(n -> right);
        delete n;
    }
}

BinTree::~BinTree(){
    deletetree(root);
}


BinTree::node* BinTree::findnode(node* n, int id) const {
    if (!n) return nullptr;   //空节点
    if (n->id == id) return n;
    //迭代寻找对应id的节点
    node* leftResult = findnode(n->left, id);
    if (leftResult) return leftResult;
    return findnode(n->right, id);
}

void BinTree::insert(int val, int parent, int flg){
    //赋值根节点
    if(parent == 0){
        if(!root){
            root = new node;
            root -> val = val;
            root -> right = nullptr;
            root -> left = nullptr;
            root -> id = current_id++;
            count++;
            depth = 1;
        }
        else{
            std::cerr << "root already exists" << std :: endl;   //异常处理
        }
        return;
    }

    //寻找双亲节点
    node* parentnode = findnode(root, parent);
    if(!parentnode){
        std::cerr << "invalid parent" << std::endl;   //异常处理
        return;
    }

    node* newnode = new node;
    newnode -> val = val;
    newnode -> left = nullptr;
    newnode -> right = nullptr;
    newnode -> id = current_id++;

    //按flg赋值
    if(flg == -1 && !parentnode -> left){
        parentnode -> left = newnode;
    }
    else if(flg == 1 && !parentnode -> right){
        parentnode -> right = newnode;
    }
    else{
        std::cerr << "node already exists" << std::endl;   //异常处理
        delete newnode;
        return;
    }

    count++;
    depth = std::max(depth, calculatedepth(root));   //更新当前二叉树深度
}

void BinTree::preorder(node* n, std::vector<int> &res) const{
    //前序遍历迭代函数
    if(n){   
        res.push_back(n -> val);
        preorder(n -> left, res);
        preorder(n -> right, res);
    }
}

int* BinTree::p_traversal() const{
    //前序遍历
    std::vector<int> res;
    preorder(root, res);
    int* ans = new int[res.size()];
    std::copy(res.begin(), res.end(), ans);
    return ans;
}

void BinTree::inorder(node* n, std::vector<int> &res) const{
    //中序遍历迭代函数
    if(n){
        inorder(n -> left, res);
        res.push_back(n -> val);
        inorder(n -> right, res);
    }
}

int* BinTree::m_traversal() const{
    //中序遍历
    std::vector<int> res;
    inorder(root, res);
    int* ans = new int[res.size()];
    std::copy(res.begin(), res.end(), ans);
    return ans;
}

void BinTree::postorder(node* n, std::vector<int> &res) const{
    //后序遍历迭代函数
    if(n){
        postorder(n -> left, res);
        postorder(n -> right, res);
        res.push_back(n -> val);
    }
}

int* BinTree::s_traversal() const{
    //后序遍历
    std::vector<int> res;
    postorder(root, res);
    int* ans = new int[res.size()];
    std::copy(res.begin(), res.end(), ans);
    return ans;
}

int BinTree::calculatedepth(node* n) const{
    if(!n) return 0;
    int leftdepth = calculatedepth(n -> left);
    int rightdepth = calculatedepth(n -> right);
    return std::max(leftdepth, rightdepth) + 1;   //比较左右子树的深度取最大值
}

int BinTree::countNode() const{
    return count;
}

int BinTree::height() const{
    return depth;
}


void BinTree::ToPThreadTree() {
    node* prev = nullptr;
    threadPreorder(prev, root);
}

void BinTree::ToMThreadTree() {
    node* prev = nullptr;
    threadInorder(prev, root);
}

void BinTree::ToSThreadTree() {
    node* prev = nullptr;
    threadPostorder(prev, root);
}

void BinTree::threadPreorder(node*& prev, node* cur) {
    if (!cur) return;
    if (prev && !prev->right) {
        prev->right = cur;
        prev->isThreadRight = true;
    }
    prev = cur;
    if (!cur->isThreadLeft) threadPreorder(prev, cur->left);
    if (!cur->isThreadRight) threadPreorder(prev, cur->right);
}

void BinTree::threadInorder(node*& prev, node* cur) {
    if (!cur) return;
    threadInorder(prev, cur->left);
    if (prev && !prev->right) {
        prev->right = cur;
        prev->isThreadRight = true;
    }
    prev = cur;
    threadInorder(prev, cur->right);
}

void BinTree::threadPostorder(node*& prev, node* cur) {
    if (!cur) return;
    threadPostorder(prev, cur->left);
    threadPostorder(prev, cur->right);
    if (prev && !prev->right) {
        prev->right = cur;
        prev->isThreadRight = true;
    }
    prev = cur;
}

int BinTree::GetLson(const int id) {
    node* target = findnode(root, id);
    if (!target || target->isThreadLeft || !target->left) {
        throw std::runtime_error("Invalid left son request");
    }
    return target->left->id;
}

int BinTree::GetRson(const int id) {
    node* target = findnode(root, id);
    if (!target || target->isThreadRight || !target->right) {
        throw std::runtime_error("Invalid right son request");
    }
    return target->right->id;
}